package com.example.algorithms.sort;

/**
 * @Author Zhang Jie
 * @Date 9/27/20
 * @Version 1.0
 */
/**
 * 冒泡排序
 * 比较两个相邻的数,如果是逆序,则交换
 * 相当于分成已排序区和未排序区
 *
 * 原地排序
 * 稳定的排序算法
 * 最好是O(n),最坏是O(n^2),平均是O(n^2)
 *
 *
 * @author jane
 */
public class BubbleSort {
    /**
     * 大的网上冒泡,大的会在数组后面
     * @param arr
     * @return
     */
    public int[] sortUp(int[] arr){
        if(arr==null||arr.length<2){
            return arr;
        }
        int length = arr.length;
        //length-1趟排序
        for(int i=0;i<length-1;i++){
            int sortedFlag=0;
            //还没有排序的区域
            for(int j=0;j<length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                    //记录是否有交换
                    sortedFlag=1;
                }

            }
            //该趟排序中没有发生,表示已经有序
            if(0==sortedFlag){
                break;
            }
        }
        return arr;
    }

    /**
     * 小的网上冒,小的数在数组后面
     * @param arr
     * @return
     */
    public int[] sortDown(int[] arr){
        if(arr.length<2){
            return arr;
        }
        for(int i=1;i<arr.length;i++){
            int sortedFlag=0;
            for(int j=0;j<arr.length-i;j++){
                if(arr[j]<arr[j+1]){
                    int temp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                    sortedFlag=1;
                }
            }
            if(0==sortedFlag){
                break;
            }
        }
        return arr;
    }
}
